The operation of Provider Backbone Bridges (PBBs), sometimes referred to as “MAC-in-MAC” or “MAC tunneling” bridges (MAC—Media Access Control), is described by the IEEE standard 802.1ah. Broadly stated, a complete PBB generally comprises a single backbone or “B” component in communication with a backbone network, and one or more instance or “I” components in communication with customer or access networks. In simple terms, the B-component bridges traffic (frames) based on outer MAC addresses (backbone or B-MACs), and the I-component bridges traffic based on inner MAC addresses (customer or C-MACs). Accordingly, for each frame traversing through a PBB bridge with both I and B components (an IB-PBB), two MAC lookup operations are required, namely, one for B-MACs (in a “B-space”) and another for C-MACs (in a “C-space”). Due to the often large number of MAC addresses in the network, these two lookup operations can be expensive and burdensome.